7. 递归的数据类型

递归与递归数据类型在编程中十分重要，许多常见的数据结构都是递归定义的。

递归数据结构的定义包括两部分：

基本情形指明该数据类型的某些不依赖递归定义得到的基本元素；
构造情形指明如何由已知的基本元素或构建的元素来构造新的元素。

类似的，定义在这些递归数据类型上的方法也是递归定义的：你需要定义该方法在所有基本情形上的值，然后定义在构造情形中，如何基于已知的方法的值得到新的值。

模棱两可的构造定义

当数据类型的递归定义允许通过多种方式得到同一个元素时，我们称这种定义方法是 模棱两可 的。实际定义递归数据结构类型时要尽可能避免模棱两可的定义，因为这极有可能导致在该数据类型上定义的递归方法存在歧义。见下面这个例子：

我们尝试以如下递归方法定义 $2$ 的所有幂的集合 $P$ ：

基本情形： $1, 2 \in P$
构造情形：若 $m, n \in P$ ，则 $m \times n \in P$

我们再定义如下方法 $f$ ：

基本情形： $f (1) = 0, f (2) = 1$
构造情形：若 $m, n \in P$ ，则 $f (m \times n) = m + f (n)$

这个定义乍看之下没有问题，但很容易就能发现 $P$ 中的大量元素可以通过多种方式构造出来，而由于 $f (m n) \neq f (n m)$ ，导致了定义的该方法存在歧义。例如 $f (16) = f (2 \times 8) = 5$ 同时 $f (16) = f (4 \times 4) = 7$ 。

然而并非所有定义在模棱两可的递归类型上的方法都存在歧义。例如将上面的方法的构造定义修改为类似取对数的运算 $f (m \times n) = f (m) + f (n)$ 就不会引发歧义。

定义递归方法或递归函数时需要十分小心！！！

首先，当我们定义的递归方法没有遵循数据类型的递归定义时，常常会发生问题。我们以在 $N$ 上定义的一些错误方法为例（ $N$ 的递归定义见下面）：

没有基本情形：

f (n) = c + f (n - 1)

有基本情形，但递归无法终止：

f (n) = {\begin{cases} 0, & n = 0 \\ f (n + 1), & otherwise \end{cases}

定义矛盾

f (n) = {\begin{cases} 0, & 2 ∣ n \\ 1, & 3 ∣ n \\ 2, & otherwise \end{cases}

为了证明递归数据结构具有某些性质，可以使用 结构归纳法。结构归纳法与上面递归方法的定义过程与前面提到的状态机上的归纳法十分相像。其基本过程为：

设 $P$ 是谓词， $R$ 是某个递归数据类型的集合， $B \subseteq R$ 是所有的基本情形， $c$ 是由已知元素构造出新元素的构造方法。则若

$\forall b \in B . P (b)$ 为真
对含有 $n$ 个参数的构造方法 $c (e_{1}, e_{2}, \dots, e_{n})$ ，有

\forall e_{i} \in R . \underset{i}{⋀} P (e_{i}) \to P (c (e_{1}, e_{2}, \dots, e_{n}))

则对于任意 $e \in R$ ， $P (e)$ 成立。

我们可以使用递归来定义非负整数集 $N$ ：

基本情形： $0 \in N$
递归情形：如果 $n \in N$ ，则 $n + 1 \in N$

如果我们在该非负整数集的定义上应用结构归纳法，会发现它和前面讲过的一般归纳法完全一致，这表明，一般归纳法是结构归纳法的特例。

然而需要注意的是，有些递归方法会使用较大的参数对应的函数值来定义较小的参数对应的函数值，这些递归方法无法使用结构归纳法来判断其性质，这些方法的递归可能无法终止，但并不绝对。例如这两个定义在 $N$ 上的经典的递归函数：

Collatz 猜想，又称冰雹猜想：

f (n) = {\begin{cases} 1, & n \leq 1 \\ f (\frac{n}{2}), & n > 1, 2 ∣ n \\ f (3 n + 1), & n > 1, 2 ∤ n \end{cases}

关于该函数一个著名猜想是 $\forall n \in N . f (n) = 1$ ，但至今仍未被证明或证伪。

阿克曼函数：

A (m, n) = {\begin{cases} 2 n, & m = 0 或 n \leq 1 \\ A (m - 1, A (m, n - 1)), & otherwise \end{cases}

阿克曼函数增长极快，对应的，其反函数 $α (x)$ 增长极慢。对于在实际过程中有意义的数据规模 $x$ ， $α (x) \leq 5$ 。 $α (x)$ 在计算并查集的时间复杂度时会用到，从实用角度而言可以看作常数。